package cn.njupt;

import java.util.HashMap;

//前缀树
public class Trie{

    private int size;
    private TrieNode root;

    static class TrieNode{
        int path;
        int end;
        HashMap<Character,TrieNode> map;
        public TrieNode(){
            path=0;
            end=0;
            map=new HashMap<>();
        }

    }

    public Trie(){
        root=new TrieNode();
    }


    public  int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void clear(){
        size=0;
        root=null;
    }


    //  字符--》TrieNode
    public void insert(String str){
        if(str==null)return;
        char[] chs=str.toCharArray();
        TrieNode parent=root;
        for (int i = 0; i <chs.length; i++) {
            TrieNode child=parent.map.get(chs[i]);
            if(child==null){
                child=new TrieNode();
                parent.map.put(chs[i],child);
            }
            child.path++;
            parent=child;
        }
        parent.end++;
        size++;

    }

    public boolean search(String str){
        TrieNode node=node(str);
        return node==null?false:node.end>0;
    }

    public boolean startsWith(String prefix){
        TrieNode node=node(prefix);
        return node==null?false:node.path>0;
    }

    public TrieNode node(String str){
        if(str==null)return null;
        char[] chs=str.toCharArray();
        TrieNode parent=root;
        for (int i = 0; i <chs.length; i++) {
            TrieNode child=parent.map.get(chs[i]);
            if(child==null){
                return null;
            }
            parent=child;
        }
        return parent;
    }

    public void delete(String str){
        if(!search(str))return;
        size--;
        char[] chs=str.toCharArray();
        TrieNode parent=root;
        for (int i = 0; i < chs.length; i++) {
            TrieNode child=parent.map.get(chs[i]);
            if(--child.path==0){
                parent.map.remove(chs[i]);
                return;
            }
            parent=child;
        }
        parent.end--;
    }

}
